#ifndef LEVEL_H
#define LEVEL_H

#include "bg_tiles.h"
#include "drawing.h"

#define ROOM_CELL_COLUMN 10
#define ROOM_CELL_ROW 6
#define MAXROOMS ROOM_CELL_COLUMN * ROOM_CELL_ROW
#define ROOM_CELL_WIDTH 256/ROOM_CELL_COLUMN-3
#define ROOM_CELL_HEIGHT 196/ROOM_CELL_ROW-10

#define TILE_WIDTH 16
#define TILE_HEIGHT 16

#define MAX_TILE_X 16
#define MAX_TILE_Y 12

enum MaskOptions {
	MO_left 	= 	0x01,
	MO_top 		= 	0x02,
	MO_right	=	0x04,
	MO_bottom	=	0x08
};

struct room
{
	s8 _top;
	s8 _bottom;
	s8 _left;
	s8 _right;
	s8 _type;		  // Start, Finish, etc...
	bool _connected;  // Whether this room connects to main path
	bool _discovered; // Map coloring
	u8 _tiles[MAX_TILE_X * MAX_TILE_Y];
};

class level
{
public:
	u8 _currentRoom;
	u8 _startingPoint;
	u8 _endingPoint;
	u16 rshift;
	u16 gshift;
	u16 bshift;
	
	room _rooms[MAXROOMS];
	bool _map;		  // Toggles viewing the whole map
	
	level();
	void SetBoundaries();
	void SetRoomDefault();
	bool CheckDistance(u8 sP, u8 eP, u8 dist);
	int  GeneratePath(u8 cR);
	void LockRoom(u8 i);
	void AddRoom(int i);
	bool TestWalls(int i);
	void GenerateTiles();
	void RandRoom(u8 i);
	void Hallways(u8 i);
	void Symmetry(u8 i);
	void CarveHole(u8 i, u8 type, u8 x, u8 y, u8 x2, u8 y2);
	void EmptyRoom(u8 i);
	void PopulateRooms();
	void RenderMap(uint16 *fb);
	void RenderCurrentRoom(uint16 *fb);
	void RenderTile(uint16 *fb, u8 x, u8 y, u8 type);
	bool CheckBlockPlacement(room r, u8 tI);
	bool TraversePath(u8 i, u8 SP, u8 EP, u8 dir);
	bool TraverseRoom(u8 i);
	bool FloodCheck(u8 i, u8 SP, u8 EP);
	void CleanRoom(u8 i);
};

level::level()
{
	PopulateRooms();
}

void level::SetBoundaries()
{
	for(u8 i = 0; i < MAXROOMS; i++)
	{
		if(i < 10) _rooms[i]._top = 0;					//Block off top walls
		if(i > MAXROOMS - 11) _rooms[i]._bottom = 0; 	//Block off bottom walls
		if(i % 10 == 0) _rooms[i]._left = 0; 			//Block off left walls
		if(i % 10 == 9 || i == 9) _rooms[i]._right = 0;	//Block off right walls
	}
}

void level::SetRoomDefault()
{
	for(u8 i=0; i < MAXROOMS; i++)
	{
		_rooms[i]._type = -1;
		_rooms[i]._top = -1;
		_rooms[i]._bottom = -1;
		_rooms[i]._left = -1;
		_rooms[i]._right = -1;
		_rooms[i]._connected = false;
		_rooms[i]._discovered = false;
		for(u8 m=0; m < MAX_TILE_X * MAX_TILE_Y; m++)
		{
			_rooms[i]._tiles[m] = 0;
		}
	}
	SetBoundaries();
	
	_rooms[_startingPoint]._type = 1;
	_rooms[_startingPoint]._discovered = true;
	_rooms[_startingPoint]._connected = true;
	
	_rooms[_endingPoint]._type = 2;
}

bool level::CheckDistance(u8 sP, u8 eP, u8 dist)
{
	u8 y1 = sP/ROOM_CELL_COLUMN;
	u8 x1 = sP - y1 * ROOM_CELL_COLUMN;
	
	u8 y2 = eP/ROOM_CELL_COLUMN;
	u8 x2 = eP - y2 * ROOM_CELL_COLUMN;
	
	if (abs(y2 - y1) < dist && abs(x2 - x1) < dist)
	{
		return false;
	}
	else
	{
		return true;
	}
}

int level::GeneratePath(u8 cR)
{
	u8 direction = rand() % 4;
	
	if (direction == 0) // UP
	{
		if (_rooms[cR]._top != 0)
		{
			if(!_rooms[cR-ROOM_CELL_COLUMN]._connected)
			{
				_rooms[cR]._top = 1;
				cR = cR - ROOM_CELL_COLUMN;
				_rooms[cR]._bottom = 1;
				//_rooms[cR]._discovered = true;
				_rooms[cR]._connected = true;
				return cR;
			}
		}
	}
	if (direction == 1) // RIGHT
	{
		if (_rooms[cR]._right != 0)
		{
			if(!_rooms[cR+1]._connected)
			{
				_rooms[cR]._right = 1;
				cR = cR + 1;
				_rooms[cR]._left = 1;
				//_rooms[cR]._discovered = true;
				_rooms[cR]._connected = true;
				return cR;
			}
		}
	}
	if (direction == 2) // BOTTOM
	{
		if (_rooms[cR]._bottom != 0)
		{
			if(!_rooms[cR+ROOM_CELL_COLUMN]._connected)
			{
				_rooms[cR]._bottom = 1;
				cR = cR + ROOM_CELL_COLUMN;
				_rooms[cR]._top = 1;
				//_rooms[cR]._discovered = true;
				_rooms[cR]._connected = true;
				return cR;
			}
		}
	}
	if (direction == 3) // LEFT
	{
		if (_rooms[cR]._left != 0)
		{
			if(!_rooms[cR-1]._connected)
			{
				_rooms[cR]._left = 1;
				cR = cR - 1;
				_rooms[cR]._right = 1;
				//_rooms[cR]._discovered = true;
				_rooms[cR]._connected = true;
				return cR;
			}
		}
	}
	return cR;
}

void level::LockRoom(u8 i)
{
	if(_rooms[i]._top == -1) //If top wall is open and...
	{
		if(!_rooms[i-ROOM_CELL_COLUMN]._connected) //Room above is not connected?
		{
			_rooms[i]._top = 0;
		}
	}
	if(_rooms[i]._bottom == -1) //If bottom wall is open and...
	{
		if(!_rooms[i+ROOM_CELL_COLUMN]._connected) //Room below is not connected?
		{
			_rooms[i]._bottom = 0;
		}
	}
	if(_rooms[i]._left== -1) //If left wall is open and...
	{
		if(!_rooms[i-1]._connected) //Room adjacent is not connected?
		{
			_rooms[i]._left = 0;
		}
	}
	if(_rooms[i]._right== -1) //If right wall is open and...
	{
		if(!_rooms[i+1]._connected) //Room adjacent is not connected?
		{
			_rooms[i]._right = 0;
		}
	}
}

void level::AddRoom(int i)
{
	int newRoom = i;
	while(newRoom == i)
	{
		int direction = rand() % 4;
		
		if (direction == 0) // UP
		{
			if (_rooms[i]._top == -1)
			{
				_rooms[i]._top = 1;
				i = i - ROOM_CELL_COLUMN;
				_rooms[i]._bottom = 1;
				//_rooms[i]._discovered = true;
				_rooms[i]._connected = true;
			}
		}
		if (direction == 1) // RIGHT
		{
			if (_rooms[i]._right == -1)
			{
				_rooms[i]._right = 1;
				i = i + 1;
				_rooms[i]._left = 1;
				//_rooms[i]._discovered = true;
				_rooms[i]._connected = true;
			}
		}
		if (direction == 2) // BOTTOM
		{
			if (_rooms[i]._bottom == -1)
			{
				_rooms[i]._bottom = 1;
				i = i + ROOM_CELL_COLUMN;
				_rooms[i]._top = 1;
				//_rooms[i]._discovered = true;
				_rooms[i]._connected = true;
			}
		}
		if (direction == 3) // LEFT
		{
			if (_rooms[i]._left == -1)
			{
				_rooms[i]._left = 1;
				i = i - 1;
				_rooms[i]._right = 1;
				//_rooms[i]._discovered = true;
				_rooms[i]._connected = true;
			}
		}
	}
}

bool level::TestWalls(int i)
{
	// 33% chance we are going to knock down a wall
	// if there is one available
	if(_rooms[i]._top == -1    || 
	   _rooms[i]._left == -1   ||
	   _rooms[i]._bottom == -1 ||
	   _rooms[i]._right == -1) 
	{
		return (!(rand() % 3));
	}
	else return false;
}

void level::GenerateTiles()
{
	for(u8 i=0; i < MAXROOMS; i++)
	{
		if(_rooms[i]._connected)
		{
			EmptyRoom(i); // Set up edges and doors
			
			//switch(rand()%3)
			switch(2)
			{
				case 0:
					Hallways(i);
					break;
				case 1:
					break;
				case 2:
					Symmetry(i);
					while(!TraverseRoom(i))
					{
						CleanRoom(i);
						Symmetry(i);
					}
					break;
			}
		}
	}
}

void level::CleanRoom(u8 i)
{
	for(u8 y = 1; y < MAX_TILE_Y - 1; y++)
	{
		for(u8 x = 1; x < MAX_TILE_X - 1; x++)
		{
			_rooms[i]._tiles[y*MAX_TILE_X + x] = 0;
		}
	}
}

//Not used because of horrible stack limitations.  Recursion BAD
bool level::TraversePath(u8 i, u8 SP, u8 EP, u8 dir)
{
	// SP --> StartingPoint
	// EP --> EndingPoint
	// i --> index into room array
	// dir --> direction from last tile (enum clockwise: left==0, top==1, right==2, bottom==3)
	
	// These keep track of what direction we can go each time TraversePath is called
	u8 doors = 0;
	
	
//All clear condition.  If our starting point is ever equal to our 
//ending point it means we had a traversable path.  yay
	if(SP == EP) 
	{
		_rooms[i]._tiles[SP] = 8;
		return true;
	}

//Look up surrounding tiles to determine where we can move
	
	//Check tile to left of current tile
	if(!(SP % MAX_TILE_X)) //Is SP currently on the left edge?
	{
		//Then we can't go left, turn bit off
		doors = doors & ~MO_left;
	}
	else 
	{
		//Else we can go left
		if(_rooms[i]._tiles[SP - 1] == 0)  doors = doors | MO_left;
	}
	
	//Check tile above current tile
	if(SP < MAX_TILE_X) //Is SP currently on the top edge?
	{
		//Then we can't go up
		doors = doors & ~MO_top;
	}
	else 
	{
		//Else we can go up
		if(_rooms[i]._tiles[SP - MAX_TILE_X] == 0)  doors = doors | MO_top;
	}
	
	//Check tile to right of current tile
	if(SP % MAX_TILE_X == MAX_TILE_X-1) //Is SP currently on the right edge?
	{
		//Then we can't go right
		doors = doors & ~MO_right;
	}
	else 
	{
		//Else we can go right
		if(_rooms[i]._tiles[SP + 1] == 0)  doors = doors | MO_right;
	}
	
	//Check tile below current tile
	if(SP > MAX_TILE_X * (MAX_TILE_Y - 1)) //Is SP currently on the bottom edge?
	{
		//Then we can't go down
		doors = doors & ~MO_bottom;
	}
	else 
	{
		//Else we can go down
		if(_rooms[i]._tiles[SP + MAX_TILE_X] == 0)  doors = doors | MO_bottom;
	}
	
	//Make sure that the direction we came from gets blocked
	//We don't want to revisit tiles (infinite recursion)
	switch(dir)
	{
		case 0:
			doors = doors & ~MO_left;
			break;
		case 1:
			doors = doors & ~MO_top;
			break;
		case 2:
			doors = doors & ~MO_right;
			break;
		case 3:
			doors = doors & ~MO_bottom;
			break;
		case 4:
			//This should be our starting case as it does nothing
			break;
	}

//Now we are ready to traverse.  We pick a direction that is available, mark it 0 (so we don't traverse it again later)
//Then we recursively call this function again.  Eventually all traversable tiles will be explored and return
//false, or we will find the endpoint and return true.

	if(doors & MO_left)
	{
		doors = doors & ~MO_left;
		_rooms[i]._tiles[SP-1] = 22;
		if(TraversePath(i, (SP-1), EP, 2 /*dir right*/)) return true;
		
	}
	if(doors & MO_top)
	{
		doors = doors & ~MO_top;
		_rooms[i]._tiles[SP-MAX_TILE_X] = 22;
		if(TraversePath(i, (SP-MAX_TILE_X), EP, 3 /*dir bottom*/)) return true;
	}
	if(doors & MO_right)
	{
		doors = doors & ~MO_right;
		_rooms[i]._tiles[SP+1] = 22;
		if(TraversePath(i, (SP+1), EP, 0 /*dir left*/)) return true;
	}
	if(doors & MO_bottom)
	{
		doors = doors & ~MO_bottom;
		_rooms[i]._tiles[SP+MAX_TILE_X] = 22;
		if(TraversePath(i, (SP+MAX_TILE_X), EP, 1 /*dir top*/)) return true;
	}	
	
	return false; //If we got back to our first function call
}

//Given a starting point, floodcheck will expand until either it finds the endpoint, or can no
//longer expand
bool level::FloodCheck(u8 i, u8 SP, u8 EP)
{
	bool done = false;
	bool changed = false;
	u8 flood_map[MAX_TILE_X*MAX_TILE_Y] = { 0 };
	for(u8 m=0; m < MAX_TILE_X*MAX_TILE_Y; m++)
	{
		flood_map[m] = 0;
	}
	
	u8 depth = 1;
	
	flood_map[SP] = depth;
	
	while (!done)
	{
		// reset our state checking bool
		changed = false;
		
		//loop through map
		for(u8 y = 1; y < MAX_TILE_Y - 1; y++)
		{
			for(u8 x = 1; x < MAX_TILE_X - 1; x++)
			{
				u8 index = y*MAX_TILE_X + x;
				if(flood_map[index] == depth)
				{
					//If our index ever equals the end point then
					//our path is solvable.
					if(index == EP) return true;
					
					// check left
					if(_rooms[i]._tiles[index - 1] == 0 && flood_map[index - 1] == 0) 
					{
						//_rooms[i]._tiles[index - 1] = 22;
						flood_map[index - 1] = depth + 1;
						changed = true;
					}
					
					// check top
					if(_rooms[i]._tiles[index - MAX_TILE_X] == 0 && flood_map[index - MAX_TILE_X] == 0)
					{
						//_rooms[i]._tiles[index - MAX_TILE_X] = 22;
						flood_map[index - MAX_TILE_X] = depth + 1;
						changed = true;
					}
					
					// check right
					if(_rooms[i]._tiles[index + 1] == 0 && flood_map[index + 1] == 0) 
					{
						//_rooms[i]._tiles[index + 1] = 22;
						flood_map[index + 1] = depth + 1;
						changed = true;
					}
					
					// check bottom
					if(_rooms[i]._tiles[index + MAX_TILE_X] == 0 && flood_map[index + MAX_TILE_X] == 0)
					{
						//_rooms[i]._tiles[index + MAX_TILE_X] = 22;
						flood_map[index + MAX_TILE_X] = depth + 1;
						changed = true;
					}
				}
			}
		}
		//end of for loops
		depth++;
		if(!changed) done = true;
	}
	
	return false;
}

//Checks paths between doors to make sure they are traversable
bool level::TraverseRoom(u8 i)
{ 
	// Represent the tile positions of the left,top,right,and bottom doors
	// 0 is the default if a door is absent in a direction
	u8 Positions[4] = {0, 0, 0, 0};
	
	// This just keeps track of how many doors in the room there are.  
	// There is a different behaviour when there is only one door
	u8 doors = 0;
	
	// Set the positions based on the doors and tally our door counter
	if(_rooms[i]._left == 1) 
	{
		doors++;
		Positions[0] = 81;
	}
	if(_rooms[i]._top == 1) 
	{
		doors++;
		Positions[1] = 23;
	}
	if(_rooms[i]._right == 1) 
	{
		doors++;
		Positions[2] = 94;
	}
	if(_rooms[i]._bottom == 1) 
	{
		doors++;
		Positions[3] = 167;
	}
	
	//Swap out position 0 with a valid door if it contains none.
	u8 m = 0;
	if(Positions[0] == 0)
	{
		for (m = 1; m < 4; m++)
		{				
			if(Positions[0] < Positions[m])
			{
				u8 tmp = Positions[0];
				Positions[0] = Positions[m];
				Positions[m] = tmp;
			}
		}
	}
	
	//When there is only one door we just try to meet in the middle
	if (doors == 1)
	{
		if(!FloodCheck(i, Positions[0], 87)) return false;
		else _rooms[i]._tiles[90] = 22;
	}
	//When we have multiple doors, we try to walk between them
	if (doors > 1)
	{
		for (m = 1; m < 4; m++)
		{
			if(Positions[m] > 0)
			{
				if(!FloodCheck(i, Positions[0], Positions[m])) return false;
			}
		}
	}
	return true;
}

//Uses the upper left quadrant to randomly build
//and then mirrors it across the other quadrants
void level::Symmetry(u8 i)
{
	//Set initial blocks for upper left quadrant.
	//We will mirror these later to create a symmetrical yet
	//random room
	u8 blocksLeft = 5;
	for(u8 y = 1; y < 6; y++)
	{
		for(u8 x = 1; x < 8; x++)
		{
			if(rand()%4 == 0) 
			{
				
				if(CheckBlockPlacement(_rooms[i], y*MAX_TILE_X + x)) 
				{
					if (blocksLeft > 0) 
					{
						_rooms[i]._tiles[y*MAX_TILE_X + x] = 15; 
						blocksLeft--;
					}
				}
			}
		}
	}
	
	//Mirror Right, Top Quadrant
	for(u8 y = 1; y < 6; y++)
	{
		for(u8 x = 1; x < 8; x++)
		{
			u8 x2 = MAX_TILE_X - x - 1;
			u8 y2 = y;
			if(CheckBlockPlacement(_rooms[i], y2*MAX_TILE_X + x2))
			{
				_rooms[i]._tiles[y2*MAX_TILE_X + x2] = _rooms[i]._tiles[y*MAX_TILE_X + x];
			}
		}
	}
	
	//Mirror Right, Bottom Quadrant
	for(u8 y = 1; y < 6; y++)
	{
		for(u8 x = 1; x < 8; x++)
		{
			u8 x2 = MAX_TILE_X - x - 1;
			u8 y2 = MAX_TILE_Y - y - 1;
			if(CheckBlockPlacement(_rooms[i], y2*MAX_TILE_X + x2))
			{
				_rooms[i]._tiles[y2*MAX_TILE_X + x2] = _rooms[i]._tiles[y*MAX_TILE_X + x];
			}
		}
	}
	
	//Mirror Left, Bottom Quadrant
	for(u8 y = 1; y < 6; y++)
	{
		for(u8 x = 1; x < 8; x++)
		{
			u8 x2 = x;
			u8 y2 = MAX_TILE_Y - y - 1;
			if(CheckBlockPlacement(_rooms[i], y2*MAX_TILE_X + x2))
			{
				_rooms[i]._tiles[y2*MAX_TILE_X + x2] = _rooms[i]._tiles[y*MAX_TILE_X + x];
			}
		}
	}
}

//Completely random block placement for a room
void level::RandRoom(u8 i)
{
	for(u8 y=1; y < MAX_TILE_Y-1; y++)
	{
		for(u8 x=1; x < MAX_TILE_X-1; x++)
		{
			u8 tIndex = y*MAX_TILE_X+x;
			// Check if we could be blocking a door before we add a block
			if(CheckBlockPlacement(_rooms[i], tIndex))
			{
				if(!((bool)(rand()%6))) _rooms[i]._tiles[tIndex] = 15;
			}
		}
	}
}

//Creates hallways between doors and then 
//randomly carves out rooms between unused areas
void level::Hallways(u8 i)
{
//Generate Hallways between doors
	//Fill whole screen with blocks
	CarveHole(i, 15, 1, 1, 14, 10);
	
	//Create path from top of screen to middle
	if(_rooms[i]._top == 1)
	{
		CarveHole(i, 0, 7, 1, 8, 6);
	}
	
	//Create path from left side of screen to middle
	if(_rooms[i]._left == 1)
	{
		CarveHole(i, 0, 1, 5, 8, 6);
	}
	
	//Create path from right side of screen to middle
	if(_rooms[i]._right == 1)
	{
		CarveHole(i, 0, 7, 5, 14, 6);
	}
	
	if(_rooms[i]._bottom == 1)
	{
		CarveHole(i, 0, 7, 5, 8, 10);
	}
	
//25% of the time we just leave hallways linear
//75% of the time we try to carve out rooms
	if(rand()%4 > 0)
	{
		//Carve out rooms like this:
		
		//ooooooooooooo oooxxxxxxxxxx
		//ooooooooooooo oooxxxxxxxxxx 
		//xxxxxxxxxxxxx oooxxxxxxxxxx
		//xxxxxxxxxxxxx oooxxxxxxxxxx
		//xxxxxxxxxxxxx oooxxxxxxxxxx
		
		// Carve out Top side of screen and create a room
		if(_rooms[i]._top != 1 && _rooms[i]._left == 1 && _rooms[i]._right == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 1, 14, 3);
			u8 hole = 4*MAX_TILE_X + ((rand()%13) + 1);
			_rooms[i]._tiles[hole] = 0;
			_rooms[i]._tiles[hole+1] = 0;
		}
		
		// Carve out Left side of screen and create a room
		if(_rooms[i]._left != 1 && _rooms[i]._top == 1 && _rooms[i]._bottom == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 1, 5, 10);
			u8 hole = MAX_TILE_X * ((rand()%9) + 1) + 6;
			_rooms[i]._tiles[hole] = 0;
			_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
		}
		
		// Carve out right side of screen and create a room
		if(_rooms[i]._right != 1 && _rooms[i]._top == 1 && _rooms[i]._bottom == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 10, 1, 14, 10);
			u8 hole = MAX_TILE_X * ((rand()%9) + 1) + 9;
			_rooms[i]._tiles[hole] = 0;
			_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
		}
		
		// Carve out bottom side of screen and create a room
		if(_rooms[i]._bottom != 1 && _rooms[i]._left == 1 && _rooms[i]._right == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 8, 14, 10);
			u8 hole = 7*MAX_TILE_X + ((rand()%13) + 1);
			_rooms[i]._tiles[hole] = 0;
			_rooms[i]._tiles[hole+1] = 0;
		}
		
		//Carve out corner rooms
		
		//oooxxxxxxxooo 
		//oooxxxxxxxooo 
		//xxxxxxxxxxxxx 
		//oooxxxxxxxooo 
		//oooxxxxxxxooo 
		
		// upper-left corner
		if(_rooms[i]._left == 1 && _rooms[i]._top == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 1, 5, 3);
			if(rand()%2 == 0)
			{
				u8 hole = MAX_TILE_X * ((rand()%2) + 1) + 6;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 4*MAX_TILE_X + ((rand()%4) + 1);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
		}
		
		// upper-right corner
		if(_rooms[i]._right == 1 && _rooms[i]._top == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 10, 1, 14, 3);
			if(rand()%2 == 0)
			{
				u8 hole = MAX_TILE_X * ((rand()%2) + 1) + 9;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 4*MAX_TILE_X + ((rand()%4) + 10);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
		}
		
		// lower-right corner
		if(_rooms[i]._right == 1 && _rooms[i]._bottom == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 10, 8, 14, 10);
			if(rand()%2 == 0)
			{
				u8 hole = MAX_TILE_X * ((rand()%2) + 8) + 9;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 7*MAX_TILE_X + ((rand()%4) + 10);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
		}
		
		// lower-left corner
		if(_rooms[i]._left == 1 && _rooms[i]._bottom == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 8, 5, 10);
			if(rand()%2 == 0)
			{
				u8 hole = MAX_TILE_X * ((rand()%2) + 8) + 6;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 7*MAX_TILE_X + ((rand()%4) + 1);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
		}
		
		//TODO: L shape areas and U shape areas.
		
		//oooooooooooo
		//oooooooooooo
		//xxxxxxxxoooo
		//xxxxxxxxoooo
		//xxxxxxxxoooo
		
		if(_rooms[i]._left == 1 && _rooms[i]._top != 1 && _rooms[i]._right != 1 && _rooms[i]._bottom == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 1, 14, 3);
			CarveHole(i, 0, 10, 1, 14, 10);
			
			if(rand()%2)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 5) + 9;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 4*MAX_TILE_X + ((rand()%6) + 1);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
			
		}
		
		//xxxxxxxxoooo
		//xxxxxxxxoooo
		//xxxxxxxxoooo
		//oooooooooooo
		//oooooooooooo
		
		if(_rooms[i]._left == 1 && _rooms[i]._top == 1 && _rooms[i]._right != 1 && _rooms[i]._bottom != 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 8, 14, 10);
			CarveHole(i, 0, 10, 1, 14, 10);
			
			if(rand()%2)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 1) + 9;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 7*MAX_TILE_X + ((rand()%6) + 1);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
			
		}
		
		//ooooxxxxxxxx
		//ooooxxxxxxxx
		//ooooxxxxxxxx
		//oooooooooooo
		//oooooooooooo
		
		if(_rooms[i]._left != 1 && _rooms[i]._top == 1 && _rooms[i]._right == 1 && _rooms[i]._bottom != 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 8, 14, 10);
			CarveHole(i, 0, 1, 1, 5, 10);
			
			if(rand()%2)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 1) + 6;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 7*MAX_TILE_X + ((rand()%6) + 7);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
			
		}
		
		//oooooooooooo
		//oooooooooooo
		//ooooxxxxxxxx
		//ooooxxxxxxxx
		//ooooxxxxxxxx
		
		if(_rooms[i]._left != 1 && _rooms[i]._top != 1 && _rooms[i]._right == 1 && _rooms[i]._bottom == 1 && rand()%2 == 0)
		{
			CarveHole(i, 0, 1, 1, 14, 3);
			CarveHole(i, 0, 1, 1, 5, 10);
			
			if(rand()%2)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 5) + 6;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			else
			{
				u8 hole = 4*MAX_TILE_X + ((rand()%6) + 7);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
			
		}
		
		//oooooooooooo
		//oooooooooooo
		//xxxxxxxxoooo
		//oooooooooooo
		//oooooooooooo
		if(_rooms[i]._left == 1 && _rooms[i]._top != 1 && _rooms[i]._right != 1 && _rooms[i]._bottom != 1)
		{
			CarveHole(i, 0, 1, 1, 14, 3);
			CarveHole(i, 0, 10, 1, 14, 10);
			CarveHole(i, 0, 1, 8, 14, 10);
			
			u8 side = rand()%3;
			
			if(side == 0)
			{
				_rooms[i]._tiles[89] = 0;
				_rooms[i]._tiles[105] = 0;
			}
			if(side == 1)
			{
				u8 hole = 4*MAX_TILE_X + ((rand()%7) + 1);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
			if(side == 2)
			{
				u8 hole = 7*MAX_TILE_X + ((rand()%7) + 1);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
		}
		
		//oooooxxooooo
		//oooooxxooooo
		//oooooxxooooo
		//oooooooooooo
		//oooooooooooo
		if(_rooms[i]._left != 1 && _rooms[i]._top == 1 && _rooms[i]._right != 1 && _rooms[i]._bottom != 1)
		{
			CarveHole(i, 0, 1, 1, 5, 10);
			CarveHole(i, 0, 10, 1, 14, 10);
			CarveHole(i, 0, 1, 8, 14, 10);
			
			u8 side = rand()%3;
			
			if(side == 0)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 1) + 6;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			if(side == 1)
			{
				_rooms[i]._tiles[119] = 0;
				_rooms[i]._tiles[120] = 0;
			}
			if(side == 2)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 1) + 9;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
		}
		
		//oooooooooooo
		//oooooooooooo
		//ooooxxxxxxxx
		//oooooooooooo
		//oooooooooooo
		if(_rooms[i]._left != 1 && _rooms[i]._top != 1 && _rooms[i]._right == 1 && _rooms[i]._bottom != 1)
		{
			CarveHole(i, 0, 1, 1, 14, 3);
			CarveHole(i, 0, 1, 1, 5, 10);
			CarveHole(i, 0, 1, 8, 14, 10);
			
			u8 side = rand()%3;
			
			if(side == 0)
			{
				_rooms[i]._tiles[86] = 0;
				_rooms[i]._tiles[102] = 0;
			}
			if(side == 1)
			{
				u8 hole = 4*MAX_TILE_X + ((rand()%7) + 7);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
			if(side == 2)
			{
				u8 hole = 7*MAX_TILE_X + ((rand()%7) + 7);
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+1] = 0;
			}
		}
		
		//oooooooooooo
		//oooooooooooo
		//oooooxxooooo
		//oooooxxooooo
		//oooooxxooooo
		if(_rooms[i]._left != 1 && _rooms[i]._top != 1 && _rooms[i]._right != 1 && _rooms[i]._bottom == 1)
		{
			CarveHole(i, 0, 1, 1, 5, 10);
			CarveHole(i, 0, 10, 1, 14, 10);
			CarveHole(i, 0, 1, 1, 14, 3);
			
			u8 side = rand()%3;
			
			if(side == 0)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 5) + 6;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
			if(side == 1)
			{
				_rooms[i]._tiles[71] = 0;
				_rooms[i]._tiles[72] = 0;
			}
			if(side == 2)
			{
				u8 hole = MAX_TILE_X * ((rand()%5) + 5) + 9;
				_rooms[i]._tiles[hole] = 0;
				_rooms[i]._tiles[hole+MAX_TILE_X] = 0;
			}
		}
	}
}

//Will flood a rectangular selection with a specific tile type (i.e. block or floor)
void level::CarveHole(u8 i, u8 type, u8 x, u8 y, u8 x2, u8 y2)
{
	for(u8 yy=y; yy <= y2; yy++)
	{
		for(u8 xx=x; xx <= x2; xx++)
		{
			_rooms[i]._tiles[yy*MAX_TILE_X+xx] = type;
		}
	}
}

// Returns true if current tile can be used for block placement
bool level::CheckBlockPlacement(room r, u8 tI)
{
	//Don't want to block the top door
	if(r._top == 1)
	{
		if(tI == 23 || tI == 24) return false;
	}
	
	//Don't want to block the bottom door
	if(r._bottom == 1)
	{
		if(tI == 167 || tI == 168) return false;
	}
	
	//Don't want to block the left door
	if(r._left == 1)
	{
		if(tI == 81 || tI == 97) return false;
	}
	
	//Don't want to block the right door
	if(r._right == 1)
	{
		if(tI == 94 || tI == 110) return false;
	}
	
	//If we got this far then the current tile is ok for placement
	return true;
}

// Set up tiles for an empty room with doors and walls
void level::EmptyRoom(u8 i)
{	
	for(u8 m = 0; m < MAX_TILE_X * MAX_TILE_Y; m++)
	{
		if (m < MAX_TILE_X) //TOP WALL
		{
			if(m == 0) _rooms[i]._tiles[m] = 11;
			else if(m == 15) _rooms[i]._tiles[m] = 12;
			else _rooms[i]._tiles[m] = 14;
		}
		
		if (!(m % MAX_TILE_X) && m > 15) //LEFT WALL
		{
			if(m == 176) _rooms[i]._tiles[m] = 9;
			else _rooms[i]._tiles[m] = 13;
		}
		
		if(m % MAX_TILE_X == MAX_TILE_X-1 && m > 15) //RIGHT WALL
		{
			if(m == 191) _rooms[i]._tiles[m] = 10;
			else _rooms[i]._tiles[m] = 16;
		}
		
		if(m > MAX_TILE_X * (MAX_TILE_Y-1) && m > 176 && m < 191) //BOTTOM WALL
		{
			_rooms[i]._tiles[m] = 17;
		}
	}
// Turn off Door tiles
	//Check Left Door
	if(_rooms[i]._left == 1)
	{
		_rooms[i]._tiles[64] = 5;
		_rooms[i]._tiles[80] = 1;
		_rooms[i]._tiles[96] = 1;
		_rooms[i]._tiles[112] = 6;
	}
	//Check Top Door
	if(_rooms[i]._top == 1)
	{
		_rooms[i]._tiles[6] = 7;
		_rooms[i]._tiles[7] = 2;
		_rooms[i]._tiles[8] = 2;
		_rooms[i]._tiles[9] = 8;
	}
	//Check Right Door
	if(_rooms[i]._right == 1)
	{
		_rooms[i]._tiles[79] = 18;
		_rooms[i]._tiles[95] = 3;
		_rooms[i]._tiles[111] = 3;
		_rooms[i]._tiles[127] = 19;
	}
	//Check Bottom Door
	if(_rooms[i]._bottom == 1)
	{
		_rooms[i]._tiles[182] = 20;
		_rooms[i]._tiles[183] = 4;
		_rooms[i]._tiles[184] = 4;
		_rooms[i]._tiles[185] = 21;
	}
}

void level::PopulateRooms()
{
// Set starting and ending points
	_map = false;
	_startingPoint = rand() % MAXROOMS;
	_endingPoint = _startingPoint;
	while(_endingPoint == _startingPoint  || !CheckDistance(_startingPoint, _endingPoint, 4))
	{
		_endingPoint = rand() % MAXROOMS;
	}
	SetRoomDefault();
	
// Generate our path from start to finish
	_currentRoom = _startingPoint;
	u8 old_room;
	u8 redundant = 0;
	while(_rooms[_currentRoom]._type != 2)
	{	
		_currentRoom = GeneratePath(_currentRoom);
		if(_currentRoom == old_room)
		{
			redundant++;
		}
		else 
		{
			redundant = 0;
		}
		
		if(redundant > 10)
		{
			redundant = 0;
			SetRoomDefault();
			_currentRoom = _startingPoint;
		}
		old_room = _currentRoom;
	}

// Branch out from main path
	for(u8 i=0; i < MAXROOMS; i++)
	{
		if(_rooms[i]._connected && _rooms[i]._type == -1)
		{
			if(TestWalls(i))
			{
				AddRoom(i);
			}
		}
	}
	
// Lock map silhouette edges
	for(u8 i=0; i < MAXROOMS; i++)
	{
		if(_rooms[i]._connected) LockRoom(i);		// Create walls for remaining sides of room
	}

// Finished connecting rooms, so lets generate tiles for the rooms
	GenerateTiles();
// Set the current room to the starting point
	_currentRoom = _startingPoint;	
}

void level::RenderMap(uint16 *fb)
{
	uint16 color;
	
	color = RGB15(0, 31, 0)  | BIT(15);
	for(u8 yRow = 0; yRow < ROOM_CELL_ROW; yRow++)
	{
		for(u8 xRow = 0; xRow < ROOM_CELL_COLUMN; xRow++)
		{	
			u8 position = yRow*ROOM_CELL_COLUMN + xRow;
			u8 xPos = (3+ROOM_CELL_WIDTH)*xRow+4;
			u8 yPos = yRow*(ROOM_CELL_HEIGHT+3)+40;
			bool discovered = _rooms[position]._discovered;
			
			// STARTING POSITION COLOR
			if (_rooms[position]._type == 1 && _rooms[position]._discovered)
			{
				color = RGB15(0, 31, 0)  | BIT(15);
			}
			// ENDING POSITION COLOR
			else if (_rooms[position]._type == 2 && (_rooms[position]._discovered || _map))
			{
				color = RGB15(31, 0, 0)  | BIT(15);
			}
			// DISCOVERED COLOR
			else if (_rooms[position]._discovered)
			{
				color = RGB15(16, 26, 26)  | BIT(15);
			}
			// UNDISCOVERED COLOR
			else
			{
				color = RGB15(5, 5, 5)  | BIT(15);
			}
	// ROOM
			if(_rooms[position]._connected)
			{
				if(discovered || _map)
					drawShape(
						xPos,					 	//X position
						yPos, 						//Y position
						ROOM_CELL_WIDTH, 			//Width
						ROOM_CELL_HEIGHT, 			//Height
						fb, 						//Buffer
						color						//Color
					);
			}
	// LOCATION		
			if(position == _currentRoom)
			{
				drawShape(
				xPos + 8,				 		//X position
				yPos + 8, 						//Y position
				(ROOM_CELL_WIDTH - 16), 		//Width
				(ROOM_CELL_HEIGHT - 16),		//Height
			    fb, 							//Buffer
				RGB15(31, 31, 0)  | BIT(15)			//Color
				);
			}
	// DOORS
			if(discovered || _map)
			{
				if(_rooms[position]._top > 0)
				{
					drawShape(
						xPos + 5, 				//X position
						yPos - 3, 				//Y position
						11, 					//Width
						3,					 	//Height
						fb, 					//Buffer
						RGB15(12, 12, 12)  | BIT(15)					//Color
					);
				}
				if(_rooms[position]._bottom > 0)
				{
					drawShape(
						xPos + 5,				//X position
						yPos + ROOM_CELL_HEIGHT,//Y position
						11, 					//Width
						3,					 	//Height
						fb, 					//Buffer
						RGB15(12, 12, 12)  | BIT(15)					//Color
					);
				}
				if(_rooms[position]._left > 0)
				{
					drawShape(
						xPos - 3,				//X position
						yPos + 5, 				//Y position
						3, 						//Width
						11,					 	//Height
						fb, 					//Buffer
						RGB15(12, 12, 12)  | BIT(15)					//Color
					);
				}
				if(_rooms[position]._right > 0)
				{
					drawShape(
						xPos + ROOM_CELL_WIDTH,	//X position
						yPos + 5, 				//Y position
						3, 						//Width
						11,					 	//Height
						fb, 					//Buffer
						RGB15(12, 12, 12)  | BIT(15)					//Color
					);
				}//END DOORS
			}
			
			// WALLS
			if(_rooms[position]._connected && (discovered || _map))
			{
				if(_rooms[position]._top == 0)
				{
					drawShape(
						xPos - 3, 				//X position
						yPos - 3, 				//Y position
						28, 					//Width
						3,					 	//Height
						fb, 					//Buffer
						RGB15(6, 4, 2) | BIT(15)		//Color
					);
				}	
				if(_rooms[position]._bottom == 0)
				{
					drawShape(
						xPos - 3, 				//X position
						yPos + ROOM_CELL_HEIGHT,//Y position
						28, 					//Width
						3,					 	//Height
						fb, 					//Buffer
						RGB15(6, 4, 2) | BIT(15)		//Color
					);
				}
				if(_rooms[position]._left == 0)
				{
					drawShape(
						xPos - 3,				//X position
						yPos - 3, 				//Y position
						3, 						//Width
						28,					 	//Height
						fb, 					//Buffer
						RGB15(6, 4, 2) | BIT(15)		//Color
					);
				}
				if(_rooms[position]._right == 0)
				{
					drawShape(
						xPos+ROOM_CELL_WIDTH,	//X position
						yPos - 3, 				//Y position
						3, 						//Width
						28,					 	//Height
						fb, 					//Buffer
						RGB15(6, 4, 2) | BIT(15)		//Color
					);
				}
			} // END WALLS
		}
	}
}

void level::RenderTile(uint16 *fb, u8 x, u8 y, u8 type)
{
	// Starting point in buffer
	u8 t = 0;
	for(unsigned short yy = y; yy < y+16; yy++)
	{
		for(unsigned short xx = x; xx < x+16; xx++)
		{
			fb[yy*SCREEN_WIDTH+xx] = bg_tiles_palette[bg_tiles_sprites[type][t]];
			t++;
		}
	}
}

void level::RenderCurrentRoom(uint16 *fb)
{
	for(u8 y = 0; y < 12; y++)
	{
		for(u8 x = 0; x < 16; x++)
		{
			RenderTile(fb, x*16, y*16, _rooms[_currentRoom]._tiles[y*MAX_TILE_X+x]);
		}
	}
}


#endif //LEVEL_H